
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2000. -- [Hnoi2010]stone 取石头游戏 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2000: [Hnoi2010]stone 取石头游戏</h2><span class=green>Time Limit: </span>20 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>36&nbsp;&nbsp;<span class=green>Solved: </span>16<br>[<a href='submitpage.php?id=2000'>Submit</a>][<a href='problemstatus.php?id=2000'>Status</a>][<a href='bbs.php?id=2000'>Discuss</a>]</center><h2>Description</h2><div class=content><p>A 公司正在举办一个智力双人游戏比赛----取石子游戏，游戏的获胜者将会获得 A 公司提<br />
供的丰厚奖金，因此吸引了来自全国各地的许多聪明的选手前来参加比赛。 <br />
与经典的取石子游戏相比，A公司举办的这次比赛的取石子游戏规则复杂了很多： <br />
&nbsp; 总共有N堆石子依次排成一行，第i堆石子有 ai个石子。 <br />
&nbsp; 开始若干堆石子已被 A公司故意拿走。 <br />
&nbsp; 然后两个玩家轮流来取石子，每次每个玩家可以取走一堆中的所有石子，但有一个限<br />
制条件：一个玩家若要取走一堆石子，则与这堆石子相邻的某堆石子已被取走(之前被<br />
某个玩家取走或开始被A公司故意拿走)。注意：第 1堆石子只与第 2堆石子相邻，第<br />
N堆石子只与第N-1堆石子相邻，其余的第 i堆石子与第i-1堆和第 i+1 堆石子相邻。&nbsp; <br />
&nbsp; 所有石子都被取走时，游戏结束。谁最后取得的总石子数最多，谁就获得了这场游戏<br />
的胜利。 <br />
作为这次比赛的参赛者之一，绝顶聪明的你，想知道对于任何一场比赛，如果先手者和后<br />
手者都使用最优的策略，最后先手者和后手者分别能够取得的总石子数分别是多少。</p></div><h2>Input</h2><div class=content><p>第一行是一个正整数N，表示有多少堆石子。输入<br />
文件第二行是用空格隔开的N个非负整数a1, a2, &hellip;, aN，其中ai表示第i堆石子有多少个石子，<br />
ai&nbsp; = 0表示第i堆石子开始被A公司故意拿走。输入的数据保证0&le;ai&le;100,000,000，并且至少有<br />
一个i使得ai = 0。30%的数据满足2&le;N&le;100，100%的数据满足2&le;N&le;1,000,000。</p></div><h2>Output</h2><div class=content><p>仅包含一行，为两个整数，分别表示都使用最优策略时，最后先手者<br />
和后手者各自能够取得的总石子数，并且两个整数间用一个空格隔开。</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>8                 <br />
1 2 0 3 7 4 0 9 </span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata> 17 9<br />
<br />
样例解释：两个玩家都使用最优策略时取走石子的顺序依次为9, 2, 1, 4, 7, 3，因此先手<br />
者取得9 + 1 + 7 = 17个石子，后手者取得2 + 4 + 3 = 9个石子。 </span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day2'>Day2</a></p></div><center>[<a href='submitpage.php?id=2000'>Submit</a>][<a href='problemstatus.php?id=2000'>Status</a>][<a href='bbs.php?id=2000'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
